class TreeNode:
    def __init__(self,env):
        self.w=env[0]
        self.h=env[1]
        self.childs=[]
class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes.sort(key=lambda x:x[0],reverse=True)
        root=TreeNode([100000000,10000000])
        def buildTree(root,node):
            if not root.childs:
                root.childs.append(node)
                return
            flag=False 
            for c in root.childs:
                if node.w<c.w and node.h<c.h:
                    flag=True
                    buildTree(c,node)
            if not flag:
                root.childs.append(node)
            return
        dep=0  
        def calcDep(node,d):
            nonlocal dep
            if not node.childs:
                if d>dep:
                    dep=d
            else:
                for c in node.childs:
                    calcDep(c,d+1)

        for e in envelopes:
            node=TreeNode(e)
            buildTree(root,node)
        calcDep(root,0)
        return dep

'''
超时
'''



class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes.sort(key=lambda x:x[0])
        dp=[0]*len(envelopes)
        result=0
        for i in range(len(envelopes)):
            maxc=0
            for j in range(i):
                if envelopes[j][0]<envelopes[i][0] and envelopes[j][1]<envelopes[i][1]:
                    if dp[j]>maxc:
                        maxc=dp[j]
            dp[i]=maxc+1
            if result<dp[i]:
                result=dp[i]
        return result

'''
执行用时：
8584 ms
, 在所有 Python3 提交中击败了
27.33%
的用户
内存消耗：
16.6 MB
, 在所有 Python3 提交中击败了
86.12%
的用户
'''